[LOJ10022]埃及分数

发表于 | 分类于 ， ， ， | | 阅读次数:

题目

题目描述

在古埃及，人们使用单位分数的和（形如1/a的，a是自然数）表示一切有理数。如：2/3=1/2+1/6，但不允许2/3=1/3+1/3，因为加数中有相同的。对于一个分数a/b，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数值越大越好。
如：

19/45=1/3+1/12+1/180
19/45=1/3+1/15+1/45
19/45=1/3+1/18+1/30
19/45=1/4+1/6+1/180
19/45=1/5+1/6+1/18

最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b（0<a<b<1000），编程计算最好的表达方式。

输入

只有一行，为a,b。（0<a<b<1000）

输出

若干个数，自小到大排列，依次是单位分数的分母，每个数字以空格隔开。

样例输入

1
19 45

样例输出

1
5 6 18

题解

埃及分数真的是一个神奇的东西，网上很多题解直接就将IDA*算法，但是为什么拿到这道题就会想到IDA*呢？

我们可以发现，本题的特别之处在于它的状态空间是无限大的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cmath>
#define MAXN 5100
typedef long long ll;
using namespace std;
ll a,b;
ll dep=0;
ll ans[MAXN],v[MAXN];
inline ll gcd(ll x,ll y){
	return y==0? x : gcd(y,x%y);
}

inline ll G_first(ll xx,ll yy) {//满足1/c<=xx/yy的最小c
	return yy/xx+1;
}

inline bool better() {
	for(int i=dep;i>=1;i--) 
		if(ans[i]!=v[i]) return ans[i]==0||v[i]<ans[i];
	return false; 
}

inline bool dfs(ll now,ll from,ll xx,ll yy){
	if(now==dep) {
		if(yy%xx) return false;//保证最后一个的xx为1（约分后
		v[now]=yy/xx;
		if(better())
			for(ll i=1;i<=dep;i++) ans[i]=v[i];  
		return true; 
	}
	bool ok=false;
	from=max(from,G_first(xx,yy));
	for(ll i=from; ;i++){
		// (dep-now+1)/i <= xx/yy 移项得
		if(yy*(dep-now+1)<=i*xx) break;//如果剩下的分数全是1/i加起来也无法超过xx/yy ,则剪去
		v[now]=i;
		ll y2=yy*i,x2=xx*i-yy;
		ll g=gcd(x2,y2);
		if(dfs(now+1,i+1,x2/g,y2/g)) ok=true;
	}
	return ok;
}
int main(){
	scanf("%lld%lld",&a,&b);
    else {
        bool ok=false;
	    for(dep=1;;dep++){
		    memset(ans,0,sizeof(ans));
		    if(dfs(1,G_first(a,b),a,b)){
			    ok=true; break;
		    }
	    }
	    if(ok) for(int i=1;i<=dep;i++) printf("%d ",ans[i]);
    }
	return 0;
}